1. 题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1: 输入: ["flower","flow","flight"] 输出: "fl"
示例 2: 输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。
说明: 所有输入只包含小写字母 a-z
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-common-prefix 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题思路
1、横向扫描
n个字符串，每次遍历比较2个字符串，一直更新最长公共前缀
2、纵向扫描
遍历所有字符串的第i个字符，寻找最先找不到相同字符的位置即可
3、分治
分治主要利用了 对两个子问题分别求解，然后对两个子问题的解计算最长公共前缀，即为原问题的解。
时间复杂度没有大的改善
4、二分
设公共最长前缀长度为x，如果x满足，则真正的公共最长公共前缀一定大于x；如果x不满足，则真正的公共最长前缀一定小于x。
所以可用二分
可惜时间复杂度还多了个logm，m为字符串数组中的字符串的最小长度
5、不完全排序
题目比较特殊，只要找到字典序最大和最小的求最长公共前缀即可
3. 代码
3.1. 横向扫描
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int size = strs.size();
if(size==1) return strs[0];
string res;
int maxlen=(1<<30);
for(int i=0;i<size-1;++i){
int minsize=min(strs[i].size(),strs[i+1].size()),j=0;
while(j<minsize&&strs[i][j]==strs[i+1][j]) j++;
if(j<maxlen){
maxlen=j;
res=strs[i].substr(0,maxlen);
}
}
return res;
}
};
一开始没注意strs可能是空的，直接用strs[0]会报错。
3.2. 纵向扫描
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int size = strs.size();
if(size==0) return "";
string res;
int maxlen=0;
for(int i=0;i<strs[0].size();++i){
for(int j=0;j<size-1;++j){
if(strs[j][i]!=strs[j+1][i]) return res;
}
res+=strs[0][maxlen++];
}
return res;
}
};
3.3. 不完全排序
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty()) return "";
auto p=minmax_element(strs.begin(),strs.end());
string res = *p.first;
for(int i=0;i< p.first->size();++i){
if(p.first->at(i)!=p.second->at(i)){
res = p.first->substr(0,i);
return res;
}
}
return res;
}
};
学会了\